Many reproduction methods are only capable of reproducing a small number of stable image tones. For example, offset printing is only capable of printing two stable tone values i.e. deposit ink or not. In order to reproduce images having continuous tones, a halftoning or screening technique is used. In the graphic arts environment, halftoning techniques convert density values of tints and images into a geometric distribution of binary dots that can be printed. The eye is not able to see the individual halftone dots, and only sees the corresponding xe2x80x9cspatially integratedxe2x80x9d density value. In a more general context, halftoning techniques can be seen as methods to convert xe2x80x9clow spatial, high tonal resolution informationxe2x80x9d into an equivalent of xe2x80x9chigh spatial, low tonal resolution informationxe2x80x9d. (The qualifiers xe2x80x9clowxe2x80x9d and xe2x80x9chighxe2x80x9d have to be seen on a relative scale in this context).
Two main classes of halftoning techniques have been described for use in the graphic arts field. These two techniques are known as xe2x80x9camplitude modulationxe2x80x9d and xe2x80x9cfrequency modulationxe2x80x9d screening. In amplitude modulation screening the halftone dots, that together give the impression of a particular tone, are arranged on a fixed geometric grid. By varying the size of the halftone dots, the different tones of images can be simulated. Consequently, his technique can also be called xe2x80x9cdot-size modulation screeningxe2x80x9d. In frequency modulation screening the distance between the halftone dots is modulated rather then their size, and can also be referred to as xe2x80x9cdot-position modulation screeningxe2x80x9d. This technique, although well known in the field of low resolution plain paper printers, has not obtained much attention for offset printing and other high end printing methods, probably because of the disadvantages to be discussed below.
Both classes of halftoning techniques are used in combination with a digital film recorder. A typical digital film recorder employs a scanning laser beam that exposes a photosensitive material at high resolution. The xe2x80x9cgridxe2x80x9d that defines the resolution at which the laser beam can be switched on or off, usually has an element size in the range of {fraction (1/1800)} of an inch. The photosensitive material can be a photographic film from which a printing plate is later prepared by means of photomechanical techniques. The smallest addressable unit on a recorder is often called a xe2x80x9cmicro dotxe2x80x9d, xe2x80x9crecorder elementxe2x80x9d, or xe2x80x9crelxe2x80x9d. Its size is referred to as the recorder xe2x80x9cpitchxe2x80x9d. As illustrated in FIG. 1A and FIG. 1B a dot-size modulated halftone dot is made up of a clustered set of recorder elements, while frequency-modulation halftone dots constitute a dispersed set of individual recording elements.
The most important characteristics of a screening or haiftoning technique for faithfully reproducing continuous tone information include:
1) The image rendering characteristics, more specifically the capability of the technique to render spatial detail in the original image content without the introduction of artifacts such as moirxc3xa9, textures and noise, as well as the capability to render a fill range of tones;
2) The photomechanical characteristics of the halftone dots produced by the method, which determine how consistently halftone dots can be recorded, copied or duplicated in the different steps of the photomechanical preparation of the printing plates; and,
3) The behavior of the halftones on an offset printing press.
The two classes of halftoning techniques, each with some of their variants, will now be reviewed in the light of the above characteristics, and their advantages and disadvantages will be discussed.
Amplitude modulation screening has as its major advantages that it has excellent photomechanical reproduction characteristics, and that, for screens with rulings up to 200 dots/inch, it prints predictably on offset presses. An important disadvantage of amplitude modulation screening, however, is the fact that unwanted patterns can occur within the halftoned image. Depending on their origin, these patterns are called subject moirxc3xa9, color moirxc3xa9 or internal moirxc3xa9. Subject moirxc3xa9 results from the geometric interaction between periodic components in the original subject matter and the halftone screen itself. Methods addressing subject moirxc3xa9 are disclosed in e.g. U.S. Pat. No. 5,130,821, EP 369302 and EP 488324. These methods do not, however, completely solve the problem.
Color moirxc3xa9 results from interferences between the halftones of the different color separations of the image. The use of screen angles for the different color separations shifted by 60 degrees with respect to each other has been suggested to address this problem. Several disclosures relate to the problem of generating screens with these angles or close approximations thereof. See for example U.S. Pat. No. 4,419,690, U.S. Pat. No. 4,350,996, U.S. Pat. No. 4,924,301 and U.S. Pat. No. 5,155,599. Other combinations of angles, frequencies or relative phases of the halftone dot patterns for the different color separations have also been used to overcome the same problem, as described for example in U.S. Pat. No. 4,443,060, U.S. Pat. No. 4,537,470 and EP 501,126.
Internal moirxc3xa9 refers to patterns resulting from the geometric interaction of the halftone screen with the addressable grid on which they are rendered. Methods to reduce internal moirxc3xa9 are usually based on the introduction of a random element that breaks up or xe2x80x9cdiffusesxe2x80x9d the phase error that periodically builds up as a consequence of the frequency and angle relation between the halftone screen and the addressable grid on which it is rendered. Examples of such techniques are disclosed in U.S. Pat. No. 4,456,924, U.S. Pat. No. 4,499,489, U.S. Pat. No. 4,700,235, U.S. Pat. No. 4,918,622, U.S. Pat. No. 5,150,428 and WO 90/04898.
None of the variants of the dot-size modulation screening has proven to be successful in completely eliminating the moirxc3xa9 problems, and frequency-modulation screening techniques have therefore been suggested to further reduce these problems. Such techniques usually produce aperiodic halftone dot distributions of which the Fourier spectrum is continuous. As is extensively discussed in the book by Ulichney Robert, xe2x80x9cDigital Halftoningxe2x80x9d, MIT Press, Cambridge Mass., 1987, ISBN 0-262-21009-6, a relationship exists between the shape of this Fourier spectrum and the graininess of the tints corresponding to the dot distributions. If this spectrum contains energy below the cut-off frequency of the human visual system, the corresponding tint has an undesirable grainy appearance. It is hence the goal to use frequency-modulation halftoning methods that minimize this low-frequency energy. This goal has lead to the concept of xe2x80x9cblue-noise halftoningxe2x80x9d, in analogy with the shape of the frequency spectrum of blue light, which also contains a reduced amount of energy at lower frequencies.
Various frequency-modulation halftone screening techniques have been disclosed and they can be divided into the following subclasses: (1) Error diffusion techniques (and their variations); (2) Point-to-point thresholding based techniques; and, (3) Special techniques, such as that disclosed in DE 29,31,092, and further developed in U.S. Pat. No. 4,485,397.
Perhaps the best known of all xe2x80x9cfrequency modulationxe2x80x9d methods is the error diffusion algorithm. It comes in many variations, but the principle is always the same: the error that occurs as a result of the binarization (or, in a more general context, the quantization) of the image data during the rendering is xe2x80x9cdiffusedxe2x80x9d to one or more of the unprocessed pixels. Best known is the Floyd and Steinberg algorithm (Floyd, R. W., and L. Steinberg, xe2x80x9cAn Adaptive Algorithm for Spatial Greyscalexe2x80x9d, Proc. SID, vol. 17/2, pp. 75-77). Many variations exist, usually differing in the number of pixels to which the error is diffused and how the error diffusion weights are randomized. The error diffusion techniques are capable of producing high quality frequency-modulation halftones, but the calculation of the quantization error and the addition of its fractions to a number of pixels makes them inherently computationally more intensive than the dot-size modulation techniques based on a point-to-point thresholding operation.
A frequency-modulation halftoning technique that enables the same performance as the point-to-point thresholding screening is based on the use of the xe2x80x9cBayerxe2x80x9d dither matrix (See Bayer, B. E., xe2x80x9cAn Optimum Method for Two-level Rendition of Continuous-tone Picturesxe2x80x9d, Proc. IEEE International Conference on Communications, Conference Record, pp. 26-11, 26-15, 1973). The Bayer dither matrix has a size that is a power of two, and contains threshold values that are arranged in such a fashion that, when thresholded against increasing levels of density, every halftone dot is xe2x80x9cas far away as possiblexe2x80x9d from the halftone dots that are used to render the lower density levels. The size of the Bayer dither matrix is usually smaller than the size of the image that is to be halftoned, and this problem is overcome by replicating the matrix horizontally and vertically, like tiles on a floor, so that a threshold value is obtained for every image pixel.
The halftone dot patterns produced by the Bayer dither matrix contain strong periodic components, visible as xe2x80x9ctexturexe2x80x9d that can potentially create moirxc3xa9 problems similar to the dot-size modulation algorithms. Because the energy of the periodic dither components is xe2x80x9cspreadxe2x80x9d over the different harmonics, and because most of these harmonics have a relatively high frequency compared to the fundamental frequency of dot-size modulation, the moirxc3xa9 that occurs is less disturbing.
Another point-to-point thresholding technique is suggested in U.S. Pat. No. 5,111,310 and is based on the use of a xe2x80x9cblue-noise maskxe2x80x9d. The blue-noise mask is a threshold array containing values that, when thresholded against pixel values, produces aperiodic halftone dot distributions that have a random, non-deterministic, non-white-noise character.
A method to calculate such a blue-noise mask is described in the specification of the cited patent, and is only summarized here. According to this method the mask is built xe2x80x9clayer-by-layerxe2x80x9d, starting at the 50% level, for incrementally increasing and decreasing threshold layers. The 50% halftone dot layer is initially seeded with a 50% random distribution of binary halftone dots. A new dot distribution is obtained containing the desired blue-noise halftoning characteristics by first converting the 50% random distribution to the two dimensional Fourier domain, multiplying it with the characteristics of a blue-noise filter, and finally reconverting this result back to the spatial domain. The next layers xe2x80x9cupxe2x80x9d and xe2x80x9cdownxe2x80x9d are obtained by selectively adding or removing additional halftone dots according to a criterion that at all levels minimizes the amount of energy in the lower part of the frequency spectrum. Because of the aperiodic character of the halftone dot distribution created by the blue-noise mask, subject moirxc3xa9 is successfully suppressed.
The large number of iterations necessary to convert back and forth between the xe2x80x9cspatialxe2x80x9d and xe2x80x9cFourierxe2x80x9d domains make the calculation of a blue-noise mask extremely time-intensive. As a result, the method is only suitable for the use of relatively small masks (e.g. 128xc3x97128 threshold values). These small masks can be used on printers that have a relatively low resolution (e.g. 300 pixels per inch). When used at the higher resolutions common in the graphic arts (e.g. 1800 pixels per inch), an objectionable pattern shows up that reflects the repetition of the aperiodic dot distribution within the mask. The problem improves by using a blue-noise mask of a larger size, but this, as mentioned earlier, leads to undesirable calculation times. Furthermore the xe2x80x9ctile repetitionxe2x80x9d patterns do not even then disappear completely, since the blue-noise method does not produce dot distributions that are sufficiently uniform to avoid visually-disturbing patterns.
In conclusion, the Bayer matrix produces periodic dot distributions that are still prone to the problems of subject moirxc3xa9, while the aperiodic dot distributions produced by the blue-noise mask technique are not sufficiently uniform to eliminate objectionable mask repetition patterns.
It is accordingly a general object of the invention to provide an improved frequency-modulation halftone screen and method for frequency-modulation halftoning yielding desirable re-prographic characteristics with minimized artifacts attributable to the screening process.
It is a specific object of the invention to provide a halftone screen in which subject moirxc3xa9 is minimized.
It is a further specific object of the invention to provide a halftone screen in which unwanted patterns are eliminated.
It is a feature of the invention that the method can be accomplished with reasonable computation resources.
The invention is a frequency-modulation halftone screen and method for making a frequency-modulation halftone screen, utilizing local randomization of a deterministic screen. The deterministic screen optimizes uniformity of the halftone dot distribution, while the local randomization suppresses artifacts due to subject moirxc3xa9. In summary, therefore, the invention can thus be described as a screen in which the uniformity of the halftone dots at a global scale is controlled deterministically to optimize the uniformity of the dot distribution, while, at a local scale, the dot distribution is randomized to reduce moirxc3xa9.